1448. 统计二叉树中好节点的数目

Similar Question

Solution Tips

方案一: Dfs

注意写法, 应该改造成标准的 sub-tree 写法

var goodNodes = function(root) {
    // dfs 记录递归回溯
    // 如何维护 path 上的最大值呢? 堆
    // 但是堆没办法回溯, 就是普通的 dfs 就行了
    let res = 0;
    dfs(Number.MIN_SAFE_INTEGER, root)
    return res;

    function dfs(max, node) {
        if (node === null) {
            return;
        }

        if (node.val >= max) {
            res++;
            max = node.val;
        }

        dfs(max, node.left);
        dfs(max, node.right);
    }
};

标准写法

var goodNodes = function(root) {
    const dfs = (root, path_max) => {
        if (root == null) {
            return 0;
        }
        let res = 0;
        if (root.val >= path_max) {
            res++;
            path_max = root.val;
        }
        res += dfs(root.left, path_max) + dfs(root.right, path_max);
        return res;
    }
    return dfs(root, -Infinity);
};